#include <assert.h>
#include <memory.h>
#include "hash_table.h"

/* Start bitmap functions. */
const uint64_t EMPTY_BLOCK = 0;
const uint64_t U64_ONE = 1;
#define MOD_64(value) ((value) & 63)
#define DIV_64(value) ((value) >> 6)
#define GET_MASK(index) (U64_ONE << MOD_64(index))
#define GET_BLOCK(bitmap, index) bitmap[DIV_64(index)]


static inline bool isBitSet(const uint64_t * const bitmap, const uint64_t index)
{
    return (GET_BLOCK(bitmap, index) & GET_MASK(index)) != EMPTY_BLOCK;
}


static inline void setBit(uint64_t *bitmap, const uint64_t index)
{
    GET_BLOCK(bitmap, index) |= GET_MASK(index);
}


static inline void clearAllBits(uint64_t *bitmap, const uint64_t bitmap_length)
{
    memset(bitmap, 0, sizeof(uint64_t) * bitmap_length);
}

/* End bitmap functions. */


#define INITIAL_HASH_TABLE_SIZE 512


static inline void *getPointer(hash_table_t *hash_table, uint16_t index)
{
    return ((uint8_t *)hash_table->table) + index * hash_table->element_size;
}


static inline void putValueInTable(hash_table_t *hash_table, void *value, const uint16_t index)
{
    void *element = getPointer(hash_table, index);

    memcpy(element, value, hash_table->element_size);
    setBit(hash_table->bitmap, index);

    hash_table->loaded_size++;
}


static void insertValueToTable(hash_table_t *hash_table, void *value)
{
    uint32_t i;
    uint16_t index;
    uint16_t hash = hash_table->hash_func(value);
    uint16_t mask = 0;

    mask = hash_table->table_size - 1;
    for (i = 0; i < hash_table->table_size; i++) {
        index = (i + hash) & mask;
        if (!isBitSet(hash_table->bitmap, index)) {
            break;
        }
    }

    putValueInTable(hash_table, value, index);
}


static inline bool isTableCrowded(hash_table_t *hash_table)
{
    return (float)hash_table->loaded_size / hash_table->table_size >= 0.7f;
}


static void rehashTable(hash_table_t *hash_table, void *new_table, uint32_t new_size)
{
    uint16_t index;
    void *old_table = hash_table->table;
    uint64_t old_bitmap[MAX_TABLE_SIZE / SIXTY_FOUR_BITS];

    memcpy(old_bitmap, hash_table->bitmap, sizeof(old_bitmap));

    hash_table->loaded_size = 0;
    hash_table->table = new_table;
    hash_table->table_size = new_size;
    clearAllBits(hash_table->bitmap, MAX_TABLE_SIZE / SIXTY_FOUR_BITS);

    for (index = 0; index < hash_table->table_size; index++) {
        if (!isBitSet(old_bitmap, index)) {
            continue;
        }

        insertValueToTable(hash_table, (uint8_t *)old_table + hash_table->element_size * index);
    }

    free(old_table);
}


static inline bool doubleTableSize(hash_table_t *hash_table)
{
    uint32_t new_size = 0;
    void *new_table = NULL;

    if (hash_table->table_size == MAX_TABLE_SIZE) {
        return false;
    }

    new_size = hash_table->table_size * 2;
    new_table = malloc(hash_table->element_size * new_size);
    if (new_table == NULL) {
        return false;
    }

    rehashTable(hash_table, new_table, new_size);

    return true;
}


hash_table_t *HashTable_NewTable(const size_t element_size, uint16_t (*hash_func)(void *value))
{
    assert(element_size != 0);
    assert(hash_func != NULL);

    hash_table_t *hash_table = malloc(sizeof(hash_table_t));
    if (hash_table == NULL) {
        return NULL;
    }

    hash_table->element_size = element_size;
    hash_table->table = malloc(element_size * INITIAL_HASH_TABLE_SIZE);
    if (hash_table->table == NULL) {
        free(hash_table);
        return NULL;
    }

    hash_table->loaded_size = 0;
    hash_table->table_size = INITIAL_HASH_TABLE_SIZE;
    clearAllBits(hash_table->bitmap, MAX_TABLE_SIZE / SIXTY_FOUR_BITS);

    hash_table->hash_func = hash_func;

    return hash_table;
}


void HashTable_DestroyTable(hash_table_t *hash_table)
{
    assert(hash_table != NULL);
    assert(hash_table->table != NULL);

    free(hash_table->table);
    hash_table->table = NULL;
    hash_table->hash_func = NULL;
    free(hash_table);
}


bool HashTable_IsValueInTable(hash_table_t *hash_table, void *value)
{
    assert(hash_table != NULL);
    assert(hash_table->table != NULL);

    uint32_t i;
    uint16_t index;
    uint16_t hash = hash_table->hash_func(value);
    uint16_t mask = hash_table->table_size - 1;

    for (i = 0; i < hash_table->table_size; i++) {
        index = (i + hash) & mask;
        if (!isBitSet(hash_table->bitmap, index)) {
            return false;
        }
        if (memcmp(value, getPointer(hash_table, index), hash_table->element_size) == 0) {
            return true;
        }
    }

    return false;
}


bool HashTable_InsertValueToTable(hash_table_t *hash_table, void *value)
{
    assert(hash_table != NULL);
    assert(hash_table->table != NULL);

    if (isTableCrowded(hash_table) && !doubleTableSize(hash_table)) {
        return false;
    }

    insertValueToTable(hash_table, value);

    return true;
}
